翻訳と辞書 Words near each other ・ Simone (actress) ・ Simone (given name) ・ Simone (surname) ・ Simone Ahuja ・ Simone Alaimo ・ Simone Aldrovandi ・ Simone Alves da Silva ・ Simone and Cino Del Duca Foundation ・ Simone Andrea Ganz ・ Simone Andreetta ・ Simone Angel ・ Simone Antonini ・ Simon's Cat ・ Simon's desert racer ・ Simon's House ・ Simon's problem ・ Simon's reagent ・ Simon's Sircus ・ Simon's spiny rat ・ Simon's Town ・ Simon's Town Museum ・ Simon's Town railway station ・ Simon's Way ・ Simon, Constable of Jerusalem ・ Simon, Count of Ponthieu ・ Simon, Count of Syracuse ・ Simon, King of the Witches ・ Simon, Metropolitan of Moscow ・ Simon, Prince of Mukhrani ・ Simon, Prince of Taranto Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Simon's problem ： ウィキペディア英語版 Simon's problem In computational complexity theory and quantum computing, Simon's problem is a computational problem in the model of decision tree complexity or query complexity, conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm, usually called Simon's algorithm, that solves the problem exponentially faster than any (deterministic or probabilistic) classical algorithm. Simon's algorithm uses $O(n)$ queries to the black box, whereas the best classical probabilistic algorithm necessarily needs at least $\backslash Omega(2^)$ queries. It is also known that Simon's algorithm is optimal in the sense that ''any'' quantum algorithm to solve this problem requires $\backslash Omega(n)$ queries. This problem yields an oracle separation between BPP and BQP, unlike the separation provided by the Deutsch-Jozsa algorithm, which separates P and EQP. Although the problem itself is of little practical value it is interesting because it provides an exponential speedup over any classical algorithm. Moreover, it was also the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms. ==Problem description and algorithm== The input to the problem is a function (implemented by a black box) $f:\backslash ^n\backslash rightarrow\; \backslash ^n$, promised to satisfy the property that for some $s\backslash in\; \backslash ^n$ we have for all $y,z\backslash in\backslash ^n$, $f(y)=f(z)$ if and only if $y=z$ or $y\; \backslash oplus\; z\; =s$. Note that the case of $s=0^n$ is allowed, and corresponds to $f$ being a permutation. The problem then is to find ''s''. The set of ''n''-bit strings is a $\backslash mathbb\_2$ vector space under bitwise XOR. Given the promise, the preimage of ''f'' is either empty, or forms cosets with ''n''-1 dimensions. Using quantum algorithms, we can, with arbitrarily high probability determine the basis vectors spanning this ''n''-1 subspace since ''s'' is a vector orthogonal to all of the basis vectors. Consider the Hilbert space consisting of the tensor product of the Hilbert space of input strings, and output strings. Using Hadamard operations, we can prepare the initial state :$\backslash sum\_x\; \backslash left|\; x\; \backslash right\backslash rangle\; \backslash left|\; 0\; \backslash right\backslash rangle$ and then call the oracle to transform this state to :$\backslash sum\_x\; \backslash left|\; x\; \backslash right\backslash rangle\; \backslash left|\; f(x)\; \backslash right\backslash rangle$ Hadamard transforms convert this state to :$\backslash sum\_y\; \backslash sum\_x\; (-1)^\; \backslash left|\; y\; \backslash right\backslash rangle\; \backslash left|\; f(x)\; \backslash right\backslash rangle$ We perform a simultaneous measurement of both registers. If $s\; \backslash cdot\; y\; =\; 1$, we have destructive interference. So, only the subspace $s\; \backslash cdot\; y\; =\; 0$ is picked out. Given enough samples of ''y'', we can figure out the ''n''-1 basis vectors, and compute ''s''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Simon's problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.